package com.zj.leetcode.easy;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 判断子序列
 * 392 is-subsequence
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class IsSubsequence {
    public static void main(String[] args) {
//        String s = "avc", t = "ahbgdc";
//        String s = "aaaaaa",t = "bbaaaa";
//        String s = "acb", t = "ahbgdc";
//        String s = "abc", t = "ahbgdc";
        String s = "",t = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        Solution solution = new IsSubsequence().new Solution();
        System.out.println(solution.isSubsequence02(s, t));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isSubsequence(String s, String t) {

            if (s.length() > t.length()) {
                return false;
            }
            int i = 0, j = 0;
            while (i < s.length() && j < t.length()) {
                if (s.charAt(i) != t.charAt(j)) {
                    ++j;
                } else {
                    ++i;
                    ++j;
                }
            }

            return i >= s.length() || j != t.length();
        }

        public boolean isSubsequence02(String s, String t){
            int n = s.length(), m = t.length();

            int[][] f = new int[m + 1][26];
            for (int i = 0; i < 26; i++) {
                f[m][i] = m;
            }

            for (int i = m - 1; i >= 0; i--) {
                for (int j = 0; j < 26; j++) {
                    if (t.charAt(i) == j + 'a')
                        f[i][j] = i;
                    else
                        f[i][j] = f[i + 1][j];
                }
            }

            System.out.println(Arrays.deepToString(f));
            return true;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}